Anshel–Anshel–Goldfeld key exchange

Anshel–Anshel–Goldfeld protocol, also known as a commutator key exchange, is a key-exchange protocol using nonabelian groups. It was invented by Drs. Michael Anshel, Iris Anshel, and Dorian Goldfeld. Unlike other group-based protocols it does not employ any commuting or commutative subgroups of a given platform group and can, in fact, use any nonabelian group with efficiently computable normal forms.

Description

Let G be a fixed nonabelian group called a platform group.

Alice's public/private information:

Alice's public key is a tuple of elements ${\overline{a}}=(a_1,\ldots,a_n)$ in G.
Alice's private key is a sequence of elements from ${\overline{a}}$ and their inverses: $a_{i_1}^{\varepsilon_1}, \ldots, a_{i_L}^{\varepsilon_L}$ , where $a_{i_k}\in{\overline{a}}$ and $\varepsilon_k=\pm 1$ . Based on that sequence she computes the product $A = a_{i_1}^{\varepsilon_1} \ldots a_{i_L}^{\varepsilon_L}$ .

Bob's public/private information:

Bob's public key is a tuple of elements ${\overline{b}}=(b_1,\ldots,b_n)$ in $G$ .
Bob's private key is a sequence of elements from ${\overline{b}}$ and their inverses: $b_{j_1}^{\delta_1}, \ldots, b_{j_L}^{\delta_L}$ , where $b_{j_k}\in{\overline{b}}$ and $\delta_k=\pm 1$ . Based on that sequence she computes the product $B = b_{j_1}^{\delta_1} \ldots b_{j_L}^{\delta_L}$ .

Transitions:

Alice sends a tuple ${\overline{b}}=(A^{-1}b_1A,\ldots,A^{-1}b_nA)$ to Bob.
Bob sends a tuple ${\overline{b}}=(B^{-1}a_1B,\ldots,B^{-1}a_nB)$ to Alice.

Shared key:

The key shared by Alice and Bob is the group element $K = A^{-1} B^{-1} A B \in G$ called the commutator of $A$ and $B$ .

Alice computes $K$ as a product $A^{-1} \cdot B^{-1}a_{i_1}^{\varepsilon_1}B\cdots B^{-1}a_{i_L}^{\varepsilon_L}B$ .
Bob computes $K$ as a product $(A^{-1}b_{i_1}^{\varepsilon_1}A \cdots A^{-1} b_{i_L}^{\varepsilon_L}A)^{-1} \cdot B = A^{-1} B^{-1} A B$ .

References

I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), pp. 287–291.

Anshel–Anshel–Goldfeld key exchange

Description

See also

References